#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_NUMBER_OF_CITIES 512

void SearchConnectedCity(char cityName[BUFSIZ]);
void SearchConnectedMinimumCost(char cityName1[BUFSIZ],
								char cityName2[BUFSIZ]);

char CityNameList[MAX_NUMBER_OF_CITIES][BUFSIZ] = { 0, };
unsigned int NumberOfCities;
int* adjacencyMatrix = 0;
int* visits = 0;

unsigned int GetCityIndex(const char* cityName);
void isReached(int v);

int main()
{
	char buf[BUFSIZ] = { 0, };
	unsigned int i;
	char ch = 0;

	puts("Welcome to my program for road planning service");
	
	printf("\nNumber of cities ? \n%%");
	scanf_s("%u", &NumberOfCities);

	// Construct AdjacencyMatrix
	adjacencyMatrix = (int*)malloc(sizeof(int)*NumberOfCities*NumberOfCities);
	if (!adjacencyMatrix) return -1;

	printf("\nNames of %d cities ?\n%%", NumberOfCities);

	for (i = 0; i < NumberOfCities; ++i)
	{
		scanf_s("%s", CityNameList[i], sizeof(CityNameList[i]));
	}

	printf("\nCosts of road construction? (For no more input, type 'n')\n");

	printf("%% ");
	fflush(stdin);
	gets_s(buf, sizeof(buf));

	while (strcmp(buf, "n"))
	{
		char lhs[BUFSIZ] = { 0, },
			rhs[BUFSIZ] = { 0, };
		int value = 0;
		unsigned int idx1 = 0, idx2 = 0;

		sscanf_s(buf, "%s $ %s = %d", lhs, sizeof(lhs), rhs, sizeof(rhs), &value);
		idx1 = GetCityIndex(lhs);
		idx2 = GetCityIndex(rhs);

		adjacencyMatrix[idx1*NumberOfCities + idx2] = 1;

		printf("%% ");
		fflush(stdin);
		gets_s(buf, sizeof(buf));
	}

	printf("\nYour request? (To stop, type 'q')\n");

	printf("%% ");
	fflush(stdin);
	gets_s(buf, sizeof(buf));

	while (strcmp(buf, "q"))
	{
		char first[BUFSIZ] = { 0, },
			second[BUFSIZ] = { 0, },
			third [BUFSIZ] = { 0, };

		sscanf_s(buf, " %s ", first, sizeof(buf));

		if (first[0] == '*')
		{
			unsigned int i;
			unsigned int destID = 0;
			int visitingCities[MAX_NUMBER_OF_CITIES] = { -1, };

			if (visits)
			{
				free(visits);
				visits = 0;
			}

			visits = (int*)malloc(sizeof(int)*NumberOfCities);
			for (i = 0; i < NumberOfCities; ++i)
			{
				visits = 0; // false
			}

			sscanf_s(buf, "%s", second, sizeof(second));

			destID = GetCityIndex(second);

			isReached(destID);

			printf("{");
			for (i = 0; i < NumberOfCities; ++i)
			{
				if (visits[i] == 1)
					printf(" %s ", CityNameList[i]);
			}
			printf("}\n");

			if (visits)
			{
				free(visits);
				visits = 0;
			}
		}
		else
		{
			sscanf_s("%s %s", second, sizeof(second), third, sizeof(third));
		}
		
		fflush(stdin);
		gets_s(buf, sizeof(buf));
	}

	printf("\nHave a happy day~\n");

	if (visits)
	{
		free(visits);
		visits = 0;
	}

	if (adjacencyMatrix)
	{
		free(adjacencyMatrix);
		adjacencyMatrix = 0;
	}

	return 0;
}

void SearchConnectedCity(char cityName[BUFSIZ])
{
}

void SearchConnectedMinimumCost(char cityName1[BUFSIZ],
								char cityName2[BUFSIZ])
{
}

unsigned int GetCityIndex(const char* cityName)
{
	unsigned int i;

	for (i = 0; i < NumberOfCities; ++i)
	{
		if (!strcmp(cityName, CityNameList[i]))
			return i;
	}

	return -1;
}

void isReached(int v)
{
	unsigned int w;
	visits[v] = 1;

	for (w = v*NumberOfCities + 0;
		w < v*NumberOfCities + NumberOfCities;
		++w)
	{
		if (!visits[w])
			isReached(w);
	}
}
